package com.test;

import java.util.Stack;

class LeetCode155 {
    private Stack stack;
    private Stack min;
    /** initialize your data structure here. */
    public LeetCode155() {
        stack  = new Stack();
        min = null;
    }
    public void push(int val) {
        stack.push(val);
        if(min==null){
            min = new Stack();
            min.push(val);
        }else{
            if((int)min.peek() > val){
                min.push(val);
            }
        }
    }

    public void pop() {
        if(min.peek()!=null && stack.peek() == min.peek()){
            min.pop();
        }
        stack.pop();
    }

    public int getMin() {
        if(min!=null && min.peek()!=null){
            return (int) min.peek();
        }
        return -1;
    }


    public static int[] sortArray(int[] nums) {
        if(nums==null || nums.length<=1){
            return nums;
        }
        int[] temp = new int[nums.length];
        sortHelper(nums,temp,0,nums.length-1);
        return nums;
    }
    static void sortHelper(int[] nums,int[] temp,int start,int end){
        if(start>=end){
            return;
        }
        int mid = (end+start)/2;
        sortHelper(nums,temp,start,mid);
        sortHelper(nums,temp,mid+1,end);
        merge(nums,temp,start,mid,mid+1,end);
    }
    static void merge(int[] nums,int[] temp,int s1,int e1,int s2,int e2){
        int i = 0;
        int j=0;
        int k = 0;
        while(i<=e1 && j<=e2){
            if(nums[i]<nums[j]){
                temp[k++] = nums[i];
                i++;
            }else{
                temp[k++] = nums[j];
                j++;
            }
        }
        while(i<=e1){
            temp[k++] = nums[i];
            i++;
        }

        while(j<=e2){
            temp[k++] = nums[j];
            j++;
        }
        for(int l = 0;l<k;l++){
            nums[s1+l] = temp[l];
        }

    }

    public static void main(String[] args) {
        int[] nums = new int[]{5,2,3,1};
        median3Num(nums,0,0+(3-1)/2,3);
    }
    static int median3Num(int[] nums,int left,int center,int right){
        if(nums[left]>nums[center]){
            if(nums[left]<nums[right]){
                return left;
            }else{
                return (nums[center]>nums[right])?center:right;
            }
        }else{
            if(nums[center]<nums[right]){
                return center;
            }else{
                return (nums[right]>nums[left])?right:left;
            }
        }
    }

}